The LDPC (Low Density Parity Check) code has a high error correction capacity and, in recent years, begins to be adopted widely in transmission systems including satellite digital broadcasting systems such as, for example, the DVB (Digital Video Broadcasting)-S.2 system used in Europe (refer to, for example, Non-Patent Document 1). Further, it is investigated to adopt the LDPC code also in terrestrial digital broadcasting of the next generation.
It is being found by recent research that a performance proximate to the Shannon limit is provided by the LDPC code as the code length is increased similarly to a turbo code and so forth. Further, since the LDPC code has a property that the minimum distance increases in proportion to the code length, it has a characteristic that it has a superior block error probability characteristic. Also it is advantageous that a so-called error floor phenomenon which is observed in a decoding characteristic of the turbo code and so forth little Occurs.
In the following, such an LDPC code as described above is described particularly. It is to be noted that the LDPC code is a linear code, and although it is not necessarily be a two-dimensional code, the following description is given under the assumption that it is a two-dimensional code.
The LDPC code has the most significant characteristic in that a parity check matrix which defines the LDPC code is a sparse matrix. Here, the sparse matrix is a matrix in which the number of those elements whose value is “1” is very small (matrix in which almost all elements are 0).
FIG. 1 shows an example of a parity check matrix H of an LDPC code.
In the parity check matrix H of FIG. 1, the weight of each column (column weight) (number of “1”) (weight) is “3” and the weight of each row (row weight) is “6.”
In encoding by LDPC codes (LDPC encoding), for example, a generator matrix G is produced based on a parity check matrix H and this generator matrix G is multiplied by two-dimensional information bits to produce a codeword (LDPC code).
In particular, an encoding apparatus which carries out LDPC encoding first calculates a generator matrix G which satisfies an expression GHT=0 together with a transposed matrix HT of a parity check matrix H. Here, if the generator matrix G is a K×N matrix, then the encoding apparatus multiplies the generator matrix G by a bit string (vector u) of K information bits to produce a codeword c (=uG) of N bits. The codeword (LDPC code) produced by the encoding apparatus is received by the reception side through a predetermined communication path.
Decoding of the LDPC code can be carried out using an algorithm proposed as probabilistic decoding (Probabilistic Decoding) by the Gallager, that is, a message passing algorithm by belief propagation on a so-called Tanner graph including a variable node (also called message node) and a check node. In the following description, each of the variable node and the check node is suitably referred to simply as node.
FIG. 2 illustrates a procedure of decoding of an LDPC code.
It is to be noted that, in the following description, a real number value where the “0” likelihood in the value of the nth code bit of an LDPC code (one codeword) received by the reception side is represented in a log likelihood ratio is suitably referred to as reception value uOi. Further, a message outputted from a check node is represented by uj and a message outputted from a variable node is represented by vi.
First, in decoding of an LDPC code, as seen in FIG. 2, an LDPC code is received and a message (check node message) uj is initialized to “0” and besides a variable k which assumes an integer as a counter of repeated processes is initialized to “0” at step S11, whereafter the processing advances to step S12. At step S12, mathematical operation represented by an expression (1) (variable node mathematical operation) is carried out based on the reception value uOi obtained by the reception of the LDPC code to determine a message (variable node message) vi. Further, mathematical operation represented by an expression (2) (check node mathematical operation) is carried out based on the message vi to determine the message uj.
      [          Expression      ⁢                          ⁢      1        ]                                            v            i                    =                                    u              oi                        +                                          ∑                                  j                  =                  1                                                                      d                    v                                    -                  1                                            ⁢                                                          ⁢                                                u                  j                                ⁢                                                                  [                                  Expression                  ⁢                                                                          ⁢                  2                                ]                                                                          (          1          )                                                          tanh            ⁡                          (                                                u                  j                                2                            )                                =                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                          tanh              ⁡                              (                                                      v                    i                                    2                                )                                                                          (          2          )                    
Here, dv and dc in the expression (1) and the expression (2) are parameters which can be selected arbitrarily and represent the number of “1s” in a vertical direction (column) and a horizontal direction (row) of the parity check matrix H. For example, in the case of a (3, 6) code, dv=3 and dc=6.
It is to be noted that, in the variable node mathematical operation of the expression (1) and the check node mathematical operation of the expression (2), the range of the mathematical operation is 1 to dv−1 or 1 to dc−1 because a massage inputted from an edge (line interconnecting a variable node and a check node) from which a message is to be outputted is not made an object of the mathematical operation. Meanwhile, the check node mathematical operation of the expression (2) is carried out by producing in advance a table of a function R(v1, v2) represented by an expression (3) defined by one output with respect to two inputs v1 and v2 and using the table successively (recursively) as represented by an expression (4).[Expression 3]x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1,v2)  (3)[Expression 4]uj=R(v1,R(v2,R(v3, . . . R(vdc−2,vdc−1)))  (4)
At step S12, the variable k is incremented by “1” further, and the processing advances to step S13. At step S13, it is decided whether or not the variable k is higher than a predetermined repeated decoding time number C. If it is decided at step S13 that the variable k is not higher than C, then the processing returns to step S12, and similar processing is repeated thereafter.
On the other hand, if it is decided at step S13 that the variable k is higher than C, then the processing advances to step S14, at which a message vi as a decoding result to be outputted finally by carrying out mathematical operation represented by an expression (5) is determined and outputted, thereby ending the decoding process of the LDPC code.
      [          Expression      ⁢                          ⁢      5        ]                                            v            i                    =                                    u              oi                        +                                          ∑                                  j                  =                  1                                                  d                  v                                            ⁢                              u                j                                                                          (          5          )                    
Here, the mathematical operation of the expression (5) is carried out, different from the variable node mathematical operation of the expression (1), using messages uj from all edges connecting to the variable node.
FIG. 3 illustrates an example of the parity check matrix H of a (3, 6) LDPC code (encoding rate: 1/2, code length: 12).
In the parity check matrix H of FIG. 3, the weight of a column is 3 and the weight of a row is 6 similarly as in FIG. 1.
FIG. 4 shows a Tanner graph of the parity check matrix H of FIG. 3.
Here, in FIG. 4, a check node is represented by “+,” and a variable node is represented by “=.” A check node and a variable node correspond to a row and a column of the parity check matrix H, respectively. A connection between a check node and a variable node is an edge and corresponds to “1” of an element of the parity check matrix.
In particular, where the element in the jth row of the ith column of the parity check matrix is 1, the ith variable node (node of “=”) from above and the jth check node (node of “+”) from above are connected by an edge. The edge represents that a code bit corresponding to the variable node has a constraint condition corresponding to the check node.
In the sum product algorithm (Sum Product Algorithm) which is a decoding method for LDPC codes, variable node mathematical operation and check node mathematical cooperation are carried out repetitively.
FIG. 5 illustrates the variable node mathematical operation carried out with regard to a variable node.
With regard to the variable node, a message vi corresponding to an edge to be calculated is determined by variable node mathematical operation of the expression (1) which uses messages u1 and u2 from the remaining edges connecting to the variable node and the reception value uOi. Also a message corresponding to any other edge is determined similarly.
FIG. 6 illustrates the check node mathematical operation carried out at a check node.
Here, the check node mathematical operation of the expression (2) can be carried out by rewriting the expression (2) into an expression (6) using the relationship of an expression a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b). It is to be noted that sign(x) is 1 where x≧0 but is −1 where x<0.
      [          Expression      ⁢                          ⁢      6        ]                                                                                            u                  j                                =                                  2                  ⁢                                                            tanh                                              -                        1                                                              ⁡                                          (                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                  tanh                          ⁡                                                      (                                                                                          v                                i                                                            2                                                        )                                                                                              )                                                                                                                                              =                                  2                  ⁢                                                            tanh                                              -                        1                                                              ⁡                                          [                                              exp                        ⁢                                                  {                                                                                    ∑                                                              i                                =                                1                                                                                                                              d                                  c                                                                -                                1                                                                                      ⁢                                                          In                              ⁡                                                              (                                                                                                                                        tanh                                    ⁡                                                                          (                                                                                                                        v                                          i                                                                                2                                                                            )                                                                                                                                                                        )                                                                                                              }                                                ×                                                                              ∏                                                          i                              =                              1                                                                                                                      d                                c                                                            -                              1                                                                                ⁢                                                      sign                            ⁡                                                          (                                                              tanh                                ⁡                                                                  (                                                                                                            v                                      i                                                                        2                                                                    )                                                                                            )                                                                                                                          ]                                                                                                                                              =                                  2                  ⁢                                                            tanh                                              -                        1                                                              ⁡                                          [                                              exp                        ⁢                                                  {                                                      -                                                          (                                                                                                ∑                                                                      i                                    =                                    1                                                                                                                                              d                                      c                                                                        -                                    1                                                                                                  ⁢                                                                  -                                                                      In                                    ⁡                                                                          (                                                                              tanh                                        ⁡                                                                                  (                                                                                                                                                                                                                                  v                                                i                                                                                                                                                                                    2                                                                                    )                                                                                                                    )                                                                                                                                                                  )                                                                                }                                                                    ]                                                        ×                                                            ∏                                              i                        =                        1                                                                                              d                          c                                                -                        1                                                              ⁢                                          sign                      ⁡                                              (                                                  v                          i                                                )                                                                                                                                                      (          6          )                    
Further, if, where x≧0, a function φ(x) is defined as an expression φ(x)=ln(tanh(x/2)), then since an expression φ−1(x)=2tanh−1(e−x) is satisfied, the expression (6) can be transformed into an expression (7).
      [          Expression      ⁢                          ⁢      7        ]                                            u            j                    =                                                    ϕ                                  -                  1                                            ⁡                              (                                                      ∑                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                      ϕ                    ⁡                                          (                                                                                                v                          i                                                                                            )                                                                      )                                      ×                                          ∏                                  i                  =                  1                                                                      d                    c                                    -                  1                                            ⁢                              sign                ⁡                                  (                                      v                    i                                    )                                                                                          (          7          )                    
At the check node, the check node mathematical operation of the expression (2) is carried out in accordance with the expression (7).
In particular, at the check node, the message uj corresponding to the edge to be calculated is determined by check node mathematical operation of the expression (7) using messages v1, v2, v3, v4 and v5 from the remaining edges connecting to the check node. Also a message corresponding to any other edge is determined in a similar manner.
It is to be noted that the function φ(x) of the expression (7) can be represented also as φ(x)=ln((ex+1)/(ex−1)), and where x>0, φ(x)=φ−1(x). When the functions φ(x) and φ−1(x) are incorporated in hardware, while they are sometimes incorporated using an LUT (Look Up Table), such LUTs become the same LUT.
Non-Patent Document 1: DVB-S.2: ETSI EN 302 307 V1.1.2 (2006-06)